package com.xiaoyu.dp;

/**
 * @program: DS_and_A
 * @description: 不同路径2
 * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
 *
 * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
 *
 * 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
 *
 * 网格中的障碍物和空位置分别用 1 和 0 来表示。
 *
 * 输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
 * 输出：2
 * 解释：
 * 3x3 网格的正中间有一个障碍物。
 * 从左上角到右下角一共有 2 条不同的路径：
 * 1. 向右 -> 向右 -> 向下 -> 向下
 * 2. 向下 -> 向下 -> 向右 -> 向右
 *
 * @author: YuWenYi
 * @create: 2021-05-24 16:24
 **/
public class UniquePathsWithObstacles_63 {
    //有障碍物,就把该点的直接置0即可
    public static int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int row = obstacleGrid.length;
        int col = obstacleGrid[0].length;

        int[][] dp = new int[row][col];

        //给第一列赋初值,注意,如果第一列中有障碍物,那么该只有障碍物之前的路才能走通!
        //所以一但出现了障碍物,那么就不需要再进行赋值了!
        for (int i = 0; i < row; i++) {
            if (obstacleGrid[i][0] != 1){
                dp[i][0] = 1;
            }else {
                break;
            }
        }
        //和给第一列赋值是同样的道理!
        for (int j = 0; j < col; j++) {
            if (obstacleGrid[0][j] != 1){
                dp[0][j] = 1;
            }else {
                break;
            }
        }
        //由于有障碍物的地方,该值是0不能变动,因此我们只需要排除这些点,让其它的点进行相加,即可!
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (obstacleGrid[i][j] != 1){
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        return dp[row-1][col-1];
    }

    //自己思路:--->使用滑动窗口进行空间优化!   --> 代码有点冗余
    public static int uniquePathsWithObstacles1(int[][] obstacleGrid) {
        int row = obstacleGrid.length;
        int col = obstacleGrid[0].length;
        //记录一行的值路之和
        int[] dp = new int[col];

        //如果只有一行,那么如果有障碍物就返回0,没有障碍物就返回1
        if (row == 1){
            for (int i = 0; i < col; i++) {
                if (obstacleGrid[0][i] == 1){
                    return 0;
                }
            }
            return 1;
        }
        //列也是同理
        if (col == 1){
            for (int i = 0; i < row; i++) {
                if (obstacleGrid[i][0] == 1){
                    return 0;
                }
            }
            return 1;
        }


        for (int i = 0; i < col; i++) {
            if (obstacleGrid[0][i] == 1) break;
            dp[i] = 1;
        }

        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                //如果第一列有障碍物,那么就把第一个数置为0就好了!
                if (obstacleGrid[i][0] == 1) dp[0] = 0;

                if (obstacleGrid[i][j] != 1){
                    //这里的解释见62题
                    dp[j] = dp[j] + dp[j-1];
                }else {
                    //如果有障碍物,就把障碍物的路径和置0
                    dp[j] = 0;
                }
            }
        }
        return dp[col-1];
    }


    //更简化版代码!
    public static int uniquePathsWithObstacles2(int[][] obstacleGrid) {
        int row = obstacleGrid.length;
        int col = obstacleGrid[0].length;

        int[] dp = new int[col];

        //起点可能有障碍物!
        dp[0] = obstacleGrid[0][0] == 1 ? 0 : 1;

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (obstacleGrid[i][j] == 1){
                    dp[j] = 0;
                }
                //j-1>=0,排除了只有一列的情况!
                if (obstacleGrid[i][j] == 0 && j-1 >= 0){
                    dp[j] += dp[j-1];
                }
            }
        }
        return dp[col-1];
    }

    public static void main(String[] args) {
        int[][] obstacleGrid = {{0,1}};
        //{0,0,0},{0,1,0},{0,0,0}
        System.out.println(uniquePathsWithObstacles2(obstacleGrid));
    }

}
